/**
 * 
 */
package linkedlist.passed2;

import java.util.HashMap;
import java.util.Map;

import linkedlist.Node;

/**
 * @author Michael
 * 
 * http://www.geeksforgeeks.org/a-linked-list-with-next-and-arbit-pointer/
 *
 */
public class CopyListWithRandomPointer {

	/**
	A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

	Return a deep copy of the list.
	*/
	/**
	 * Definition for singly-linked list with a random pointer.
	 */
	class RandomListNode {
		int label;
	    RandomListNode next, random;
	    RandomListNode(int x) { this.label = x; }
	};
	 
    public RandomListNode copyRandomList(RandomListNode head) {
    	RandomListNode currNode = head;
    	while (currNode != null) {
    		RandomListNode newNode = new RandomListNode(currNode.label);
    		newNode.next = currNode.next;
    		currNode.next = newNode;
    		currNode = newNode.next;
    	}
    	
    	//update random
    	currNode = head;
    	while (currNode != null) {
    		RandomListNode newNode = currNode.next;
    		newNode.random = currNode.random == null ? null : currNode.random.next;
    		currNode = newNode.next;
    	}
    
    	//update next;
    	RandomListNode newHead = head.next;
    	currNode = head;
    	while (currNode.next != null) {
    		RandomListNode nextNode = currNode.next;
    		currNode.next = nextNode.next;
    		currNode = nextNode;
    	}
    	
    	return newHead;
    }
	
	public static class NodeWithRandomPointer<E extends Comparable<? super E>>
			extends Node<E> {
		public NodeWithRandomPointer<E> random;
		public NodeWithRandomPointer<E> next;

		public NodeWithRandomPointer(E value) {
			super(value);
		}

		public NodeWithRandomPointer<E> clone() {
			return this.cloneBest();
		}

		public NodeWithRandomPointer<E> cloneBest() {

			NodeWithRandomPointer<E> head = this, curr = head;

			while (curr != null) {
				NodeWithRandomPointer<E> newNode = new NodeWithRandomPointer<E>(
						curr.value);
				newNode.next = curr.next;
				curr.next = newNode;
				curr = newNode.next;
//				NodeWithRandomPointer<E> newNode = new NodeWithRandomPointer<E>(
//						curr.value);
//				NodeWithRandomPointer<E> next = curr.next;
//				curr.next = newNode;
//				newNode.next = next;
//				curr = next;
			}

			// update random
			curr = head;
			while (curr != null) {
				NodeWithRandomPointer<E> newCurr = curr.next;
				newCurr.random = curr.random == null ? null : curr.random.next;
				curr = newCurr.next;
			}

			// update next
			NodeWithRandomPointer<E> newHead = head.next;
			curr = head;
			while (curr.next != null) {
				NodeWithRandomPointer<E> next = curr.next;
				curr.next = next.next;
				curr = next;
			}

			return newHead;
		}

		public NodeWithRandomPointer<E> cloneHT1() {
			HashMap<NodeWithRandomPointer<E>, NodeWithRandomPointer<E>> map = new HashMap<NodeWithRandomPointer<E>, NodeWithRandomPointer<E>>();

			NodeWithRandomPointer<E> head = this, curr = head, newHead = null, newPrev = null;
			while (curr != null) {
				NodeWithRandomPointer<E> newNode = new NodeWithRandomPointer<E>(
						curr.value);
				map.put(curr, newHead);
				if (null == newHead) {
					newHead = newNode;
				}
				if (newPrev != null) {
					newPrev.next = newNode;
				}
				curr = curr.next;
				newPrev = newNode;
			}

			//update random
			curr = head;
			NodeWithRandomPointer<E> newCurr = newHead;
			while (curr != null) {
				newCurr.random = curr.random == null ? null : map
						.get(curr.random);
				curr = curr.next;
				newCurr = newCurr.next;
			}

			return newHead;
		}

		/*
		 * Time O(n), Space O(n)
		 */
		public NodeWithRandomPointer<E> cloneHT() {

			Map<NodeWithRandomPointer<E>, NodeWithRandomPointer<E>> map = new HashMap<NodeWithRandomPointer<E>, NodeWithRandomPointer<E>>();

			NodeWithRandomPointer<E> newHead = null;
			NodeWithRandomPointer<E> head = this;
			NodeWithRandomPointer<E> prev = head; // 
			NodeWithRandomPointer<E> curr = null;
			// build with next 
			while (prev != null) {
				NodeWithRandomPointer<E> node = new NodeWithRandomPointer<E>(
						prev.value);
				map.put(prev, node);
				if (null == newHead) {
					newHead = node;
				}
				if (curr != null) {
					curr.next = node;
				}
				curr = node;
				prev = prev.next;
			}

			// build with random
			prev = head;
			while (prev != null) {
				if (prev.random != null) {
					map.get(prev).random = map.get(prev.random);
				}
				prev = prev.next;
			}

			return newHead;
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		NodeWithRandomPointer<Integer> head = new NodeWithRandomPointer<Integer>(
				0);
		NodeWithRandomPointer<Integer> n1 = new NodeWithRandomPointer<Integer>(
				1);
		NodeWithRandomPointer<Integer> n2 = new NodeWithRandomPointer<Integer>(
				2);
		NodeWithRandomPointer<Integer> n3 = new NodeWithRandomPointer<Integer>(
				3);
		head.next = n1;
		n1.next = n2;
		n2.next = n3;
		n3.next = null;
		head.random = n3;
		n1.random = null;
		n2.random = n1;
		n3.random = n2;

		NodeWithRandomPointer<Integer> n = head;
		while (n != null) {
			System.out.println("curr: " + n.value + " random:"
					+ (n.random != null ? n.random.value : "null"));
			n = n.next;
		}
		System.out.println();

		NodeWithRandomPointer<Integer> newHead = head.clone();
		n = newHead;
		while (n != null) {
			System.out.println("curr: " + n.value + " random:"
					+ (n.random != null ? n.random.value : "null"));
			n = n.next;
		}

	}

	/**
	 * 
	 */
	public CopyListWithRandomPointer() {
		// TODO Auto-generated constructor stub
	}

}
